package com.leetcode.partition6;

import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/11/1 17:40
 */
public class LC560和为K的子数组 {

    public static int subarraySum(int[] nums, int k) {
        return prefixSum(nums, k);
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        System.out.println(subarraySum(nums, 1));
    }

    private static int prefixSum(int[] nums, int k) {
        //prefix[j]-prefix[i]=k  ->  prefix[i]=prefix[j]-k，推导公式指出后一项只依赖于前一项，因此不需要申请一个前缀数组来存放前缀和
        int answer = 0, curSum = 0;
        //key为当前前缀和与k的差，value为差值出现的次数，因为样例存在负数和0的情况，prefixSums也可能出现0，因此用HashMap的value表示出现的次数
        Map<Integer, Integer> cache = new HashMap<>();
        //当前缀和等于k时，哈希表中还没有存入curSum-k=0这一项，所以进行手动设置
        cache.put(0, 1);
        for (int j = 0; j < nums.length; j++) {
            curSum += nums[j];
            if (cache.containsKey(curSum - k)) {
                answer += cache.get(curSum - k);
            }
            cache.put(curSum, cache.getOrDefault(curSum, 0) + 1);
        }
        return answer;
    }
}
